package com.xx.springboot.DataStructure.LeetCode.BST;

/**

     给定一个二叉树，找出其最大深度。

     二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

     说明: 叶子节点是指没有子节点的节点。

     示例：
     给定二叉树 [3,9,20,null,null,15,7]，

     3
     / \
     9  20
     /  \
     15   7
     返回它的最大深度 3 。
 */
public class maxDepth {

    /**
     *
     *
     * 递归查找 二叉树的最大深度
     * 1.判断极端情况, 如果传入的二叉树是null 那么返回 0
     * 2.当传入的二叉树 左子树为空, 那么应该继续使用右子树 进行递归, 并且深度加 1
     * 3.当传入的二叉树 右子树为空, 那么应该继续使用左子树 进行递归, 并且深度加 1
     * 4.当传入的二叉树 左右子树都不为空, 那么应该对左右字树 分别判断,然后去深度最大的字数 进行返回
     *
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        if(root.left == null)
            return maxDepth(root.right) + 1;

        if(root.right ==  null)
            return maxDepth(root.left) + 1;

        return max(maxDepth(root.left) + 1, maxDepth(root.right) + 1) ;
    }

    /**
     * 获取得到两个值中的最大值
     * @param a
     * @param b
     * @return
     */
    public int max(int a, int b){
        return a > b ? a : b;
    }

    public int maxDepth1(TreeNode root) {
        if(root == null)
            return 0;
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        return 1 + (l > r ? l : r);
    }
}
